package com.jacky.javafx.graph;

import javafx.util.Pair;

import java.lang.reflect.Array;
import java.util.*;

public class Graph {

    private final int[][] matrix;
    private int vertices;

    private int counter;

    public Graph() {
        matrix = new int[30][30];
        vertices = 0;
    }

    Graph(int size) {
        matrix = new int[size][size];
        vertices = 0;
    }

    public void insertVertx() {
        vertices++;
    }

    public void insertEdge(int u, int v, int weight) {
        matrix[u][v] = weight;
        matrix[v][u] = weight;
    }

    public void display() {
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
//                System.out.println("matrix[" + i + "][" + j + "]=" + matrix[i][j]);
            }
        }
    }

    public Pair<ArrayList<Integer>, Boolean> dfs(int source, int destination) {
        ArrayList<Integer> layersDFS = new ArrayList<>();
        boolean[] visited = new boolean[vertices];

        visited[source] = true;
        dfsCall(source, visited, layersDFS);
        Boolean destinationFound = visited[destination];
        return new Pair<>(layersDFS, destinationFound);
    }

    public void dfsCall(int curr, boolean[] visited, ArrayList<Integer> layer) {
        visited[curr] = true;
        layer.add(curr);

        for (int i = 0; i < vertices; i++) {
            if (!visited[i] && matrix[curr][i] != 0) {
                dfsCall(i, visited, layer);
            }
        }
    }

    public Pair<ArrayList<ArrayList<Integer>>, ArrayList<Integer>> bfs(int source, int destination) {
        ArrayList<ArrayList<Integer>> layers = new ArrayList<>();
        ArrayList<Integer> layer = new ArrayList<>();

        boolean[] visited = new boolean[vertices];
        int[] parent = new int[vertices];
        parent[source] = -1;

        Queue<Integer> q = new LinkedList<>();
        q.add(source);

        visited[source] = true;
        int count = 1;
        int next_count = 0;
        while (!q.isEmpty()) {
            boolean isDestinationLayer = false;
            int curr = q.remove();
            layer.add(curr);
            count--;

            if (curr == destination) {
                isDestinationLayer = true;
            }
            for (int i = 0; i < vertices; i++) {
                if (matrix[curr][i] != 0 && (!visited[i])) {
                    q.add(i);
                    next_count++;
                    parent[i] = curr;
                    visited[i] = true;
                }
            }
            if (count == 0) {
                layers.add((ArrayList<Integer>) layer.clone());
                layer.clear();

                if (isDestinationLayer) break;

                count = next_count;
                next_count = 0;
            }
        }

        System.out.println("before path");
        ArrayList<Integer> reversePath = new ArrayList<>();
        if (!visited[destination]) {
            return new Pair<>(layers, reversePath);
        }
        int curr = destination;
        while (curr != -1) {
            reversePath.add(curr);
            curr = parent[curr];
        }

        System.out.println("after path");
        return new Pair<>(layers, reversePath);
    }

    public void component_dfs(int curr, int component, int[] visited) {
        visited[curr] = component;
        for (int i = 0; i < vertices; i++) {
            if (matrix[curr][i] != 0 && visited[i] == 0) {
                component_dfs(i, component, visited);
            }
        }
    }

    public ArrayList<ArrayList<Integer>> getComponents() {

        ArrayList<ArrayList<Integer>> components = new ArrayList<>();
        int[] visited = new int[vertices];
        int component = 0;

        for (int i = 0; i < vertices; i++) {
            if (visited[i] == 0) {
                component++;
                component_dfs(i, component, visited);

                ArrayList<Integer> temp = new ArrayList<>();
                for (int node = 0; node < vertices; node++) {
                    if (visited[node] == component) {
                        temp.add(node);
                    }
                }
                components.add(temp);
            }
        }
        return components;
    }

    public Pair<ArrayList<Integer>, ArrayList<Integer>> dijkstra(int source, int destination) {
        boolean[] visited = new boolean[vertices];
        int[] distance = new int[vertices];
        for (int i = 0; i < vertices; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        distance[source] = 0;

        int[] parent = new int[vertices];
        parent[source] = -1;

        PriorityQueue<Node> pq = new PriorityQueue<>(vertices, new Node());
        pq.add(new Node(source, distance[source]));

        ArrayList<Integer> layer = new ArrayList<>();
        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            int currNode = curr.node;
            int currDist = curr.cost;

            visited[currNode] = true;
            layer.add(currNode);
            if (currNode == destination) {
                break;
            }
            if (currDist > distance[currNode]) {
                System.out.println(currNode + " " + currDist);
                continue;
            }
            for (int i = 0; i < vertices; i++) {
                if (matrix[currNode][i] != 0 && !visited[i] && distance[currNode] + matrix[currNode][i] < distance[i]) {
                    parent[i] = currNode;
                    distance[i] = distance[currNode] + matrix[currNode][i];
                    pq.add(new Node(i, distance[i]));
                }
            }
        }

        ArrayList<Integer> reversePath = new ArrayList<>();
        if (!visited[destination]) {
            return new Pair<>(layer, reversePath);
        }

        System.out.println("before path");
        int curr = destination;
        while (curr != -1) {
            reversePath.add(curr);
            System.out.println("curr:" + curr);
            curr = parent[curr];
        }
        System.out.println("after path");
        return new Pair<>(layer, reversePath);
    }

    public ArrayList<Pair<Integer, Integer>> getSpanningTree() {
        ArrayList<Pair<Integer, Integer>> edgeList = new ArrayList<>();
        boolean[] visited = new boolean[vertices];
        PriorityQueue<Edge> pq = new PriorityQueue<>((vertices * vertices) / 2, new Edge());

        for (int i = 0; i < vertices; i++) {
            for (int j = i; j < vertices; j++) {
                if (matrix[i][j] > 0) {
                    pq.add(new Edge(i, j, matrix[i][j]));
                }
            }
        }

        DisjointUnionSet disjointUnionSet = new DisjointUnionSet(vertices);
        int count = vertices - 1;
        while (count != 0 && pq.size() > 0) {
            Edge currEdge = pq.poll();
            if (!disjointUnionSet.isFromSameComponent(currEdge.source, currEdge.destination)) {
                edgeList.add(new Pair<>(currEdge.source, currEdge.destination));
                disjointUnionSet.union(currEdge.source, currEdge.destination);

                visited[currEdge.source] = true;
                visited[currEdge.destination] = true;
                count--;
            }
        }

        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                System.out.println("edgeList:" + edgeList);
                System.out.println(i);
                return new ArrayList<>();
            }
        }
        return edgeList;
    }

    public ArrayList<Pair<Integer, Integer>> getBridges() {
        ArrayList<Pair<Integer, Integer>> bridges = new ArrayList<>();
        int[] tim = new int[vertices];
        int[] low = new int[vertices];
        boolean[] visited = new boolean[vertices];

        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                counter = 0;
                dfsOfBridge(i, -1, tim, low, visited, bridges);
            }
        }
        return bridges;
    }

    private void dfsOfBridge(int curr, int parent, int[] tim, int[] low, boolean[] visited, ArrayList<Pair<Integer, Integer>> bridges) {
        tim[curr] = low[curr] = counter;
        counter++;
        visited[curr] = true;

        for (int i = 0; i < vertices; i++) {
            if (matrix[curr][i] == 0 || i == parent) {
                continue;
            }
            if (!visited[i]) {
                dfsOfBridge(i, curr, tim, low, visited, bridges);
                if (low[i] < low[curr]) {
                    low[curr] = low[i];
                }
                if (low[i] > tim[curr]) {
                    bridges.add(new Pair<>(curr, i));
                }
            } else {
                if (tim[i] < low[curr]) {
                    low[curr] = tim[i];
                }
            }
        }
    }

    public Set<Integer> getArticulationPoints() {
        Set<Integer> articulationPoints = new HashSet<>();
        int[] tim = new int[vertices];
        int[] low = new int[vertices];
        boolean[] visited = new boolean[vertices];

        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                counter = 0;
                dfsOfArticulation(i, -1, tim, low, visited, articulationPoints);
            }
        }
        return articulationPoints;
    }

    private void dfsOfArticulation(int curr, int parent, int[] tim, int[] low, boolean[] visited, Set<Integer> articulationPoints) {
        tim[curr] = low[curr] = counter;
        counter++;
        visited[curr] = true;

        int child = 0;
        for (int i = 0; i < vertices; i++) {
            if (matrix[curr][i] == 0 || i == parent) {
                continue;
            }
            if (!visited[i]) {
                child++;
                dfsOfArticulation(i, curr, tim, low, visited, articulationPoints);
                if (low[i] < low[curr]) {
                    low[curr] = low[i];
                }
                if (low[i] >= tim[curr] && parent != -1) {
                    System.out.println("point:" + curr);
                    articulationPoints.add(curr);
                }
            } else {
                if (tim[i] < low[curr]) {
                    low[curr] = tim[i];
                }
            }
        }
        if (parent == -1 && child > 1) {
            articulationPoints.add(curr);
        }
    }

    public void reset() {
        vertices = 0;
        for (int i = 0; i < 30; i++) {
            for (int j = 0; j < 30; j++) {
                matrix[i][j] = 0;
            }
        }
    }

    public int[][] getMatrix() {
        return matrix;
    }

    public int getVerticesCount() {
        return vertices;
    }
}
